package com.structure.algorithm;

/**
 * 整体思路是先创建一个dummy节点，然后将要排序的节点放到dummy节点的next上，最后将dummy.next返回即可
 * Created by 乔磊 on 2015/11/30.
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        //新创建一个临时的节点
        ListNode dummy = new ListNode(0);
        //判断传入的节点是否为空
        while (head != null) {
            //将dummy的地址赋给node，让node与dummy使用同一个地址，这样修改node的时候，dummy也随着一起改变
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }

        return dummy.next;
    }
    public static void main(String[] args){
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        new InsertionSortList().insertionSortList(head);
       /* ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        node.next = new ListNode(200);
        System.out.print(dummy.next.val);

        StringBuffer a = new StringBuffer("abc");
        StringBuffer b = a;
        b.append("aaa");
        System.out.print(a.toString());*/
    }
}
